Binary Tree Right Side View || Populating Next Right Pointers in Each Node

Binary Tree Right Side View

Question

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:

Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Analysis

Version 1

• Each depth of the tree only select one node.
• View depth is current size of result list.

Version 2

• 层次遍历，在parent==0即要换层次的时候将当前节点的值加入res

Code

Version 1

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);
        
    }
}

Version 2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null)  return res;
        Queue<TreeNode> queue=new LinkedList();
        queue.offer(root);
        int parent=1;
        int child=0;
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
                child++;
            }
            if(node.right!=null){
                queue.offer(node.right);
                child++;
            }
            if(--parent==0){
                parent=child;
                child=0;
                res.add(node.val);
            }
        }
        return res;
    }
}

Populating Next Right Pointers in Each Node

Question

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,

Given the following binary tree,

1
     /  \
    2    3
   / \    \
  4   5    7

After calling your function, the tree should look like:

1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

Analysis

Version 1 见注释

Version 2 层次遍历，每次除了最后一个节点next=null，其余的next=当前队列最上层节点

Code

Version 1 (LeetCode Version)

public class Solution {
    
    //based on level order traversal
    public void connect(TreeLinkNode root) {

        TreeLinkNode head = null; //head of the next level
        TreeLinkNode prev = null; //the leading node on the next level
        TreeLinkNode cur = root;  //current node of current level

        while (cur != null) {
            
            while (cur != null) { //iterate on the current level
                //left child
                if (cur.left != null) {
                    if (prev != null) {
                        prev.next = cur.left;
                    } else {
                        head = cur.left;
                    }
                    prev = cur.left;
                }
                //right child
                if (cur.right != null) {
                    if (prev != null) {
                        prev.next = cur.right;
                    } else {
                        head = cur.right;
                    }
                    prev = cur.right;
                }
                //move to next node
                cur = cur.next;
            }
            
            //move to next level
            cur = head;
            head = null;
            prev = null;
        }
        
    }
}

Version 2

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)  return;
        Queue<TreeLinkNode> q=new LinkedList<TreeLinkNode>();
        q.offer(root);
        int parent=1;
        int child=0;
        while(!q.isEmpty()){
            TreeLinkNode node=q.poll();
            if(node.left!=null){
                q.offer(node.left);
                child++;
            }
            if(node.right!=null){
                q.offer(node.right);
                child++;
            }
            if(--parent==0){
                node.next=null;
                parent=child;
                child=0;
            }else{
                node.next=q.peek();
            }
        }
    }
}